﻿#region CPL License

/*
    Nuclex Framework
    Copyright (C) 2002-2009 Nuclex Development Labs

    This library is free software; you can redistribute it and/or
    modify it under the terms of the IBM Common Public License as
    published by the IBM Corporation; either version 1.0 of the
    License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    IBM Common Public License for more details.
*/

#endregion

#region using statements

using System;
using System.Collections;
using System.Collections.Generic;

#endregion

namespace XNAGameEngine.DataStructures
{
    /// <summary>
    /// A double-ended queue that allocates memory in _blocks
    /// </summary>
    /// <typeparam name="TItemType">Type of the items being stored in the queue</typeparam>
    /// <remarks>
    ///   <para>
    ///     The double-ended queue allows items to be appended to either side of the queue
    ///     without a hefty toll on performance. Like its namesake in C++, it is implemented
    ///     using multiple arrays.
    ///   </para>
    ///   <para>
    ///     Therefore, it's not only good at coping with lists that are modified at their
    ///     beginning, but also at handling huge data sets since enlarging the deque doesn't
    ///     require items to be copied around and still can be accessed by index.
    ///   </para>
    /// </remarks>
    public class Deque<TItemType> : IList<TItemType>, IList
    {
        #region local classes

        /// <summary>
        /// Enumerates over the items in a _deque
        /// </summary>
        private class Enumerator : IEnumerator<TItemType>
        {
            /// <summary>
            /// Initializes a new _deque enumerator
            /// </summary>
            /// <param name="deque">Deque whose items will be enumerated</param>
            public Enumerator(Deque<TItemType> deque)
            {
                _deque = deque;
                _blockSize = _deque._blockSize;
                _lastBlock = _deque._blocks.Count - 1;
                _lastBlockEndIndex = _deque._lastBlockEndIndex - 1;

                Reset();
            }

            /// <summary>
            /// Immediately releases all resources owned by the instance
            /// </summary>
            public void Dispose()
            {
                _deque = null;
                _currentBlock = null;
            }

            /// <summary>
            /// The item at the enumerator's current position
            /// </summary>
            public TItemType Current
            {
                get
                {
#if DEBUG
                    CheckVersion();
#endif

                    if (_currentBlock == null)
                    {
                        throw new InvalidOperationException(
                            "Enumerator is not on a valid position");
                    }

                    return _currentBlock[_subIndex];
                }
            }

            /// <summary>
            /// Advances the enumerator to the next item
            /// </summary>
            /// <returns>True if there was a next item</returns>
            public bool MoveNext()
            {
#if DEBUG
                CheckVersion();
#endif

                // If we haven't reached the last block yet      
                if (_currentBlockIndex < _lastBlock)
                {
                    // Advance to the next item. If the end of the current block is reached,
                    // go to the next block's first item
                    ++_subIndex;
                    if (_subIndex >= _blockSize)
                    {
                        ++_currentBlockIndex;
                        _currentBlock = _deque._blocks[_currentBlockIndex];
                        _subIndex = _currentBlockIndex == 0
                                        ? _deque._firstBlockStartIndex : 0;
                    }

                    // Item found. If the current block wasn't the last block, an item *has*
                    // to follow since otherwise, no further _blocks would exist!
                    return true;
                }

                // We in or beyond the last block
                // Are there any items left to advance to?
                if (_subIndex < _lastBlockEndIndex)
                {
                    ++_subIndex;
                    return true;
                }

                // Nope, we've reached the end of the _deque
                _currentBlock = null;
                return false;
            }

            /// <summary>
            /// Resets the enumerator to its initial position
            /// </summary>
            public void Reset()
            {
                _currentBlock = null;
                _currentBlockIndex = -1;
                _subIndex = _deque._blockSize - 1;

#if DEBUG
                _expectedVersion = _deque._version;
#endif
            }

            /// <summary>
            /// The item at the enumerator's current position
            /// </summary>
            object IEnumerator.Current
            {
                get { return Current; }
            }

#if DEBUG
            /// <summary>
            /// Ensures that the _deque has not changed
            /// </summary>
            private void CheckVersion()
            {
                if (_expectedVersion != _deque._version)
                    throw new InvalidOperationException(
                        "Deque has been modified");
            }
#endif

            /// <summary>
            /// Deque the enumerator belongs to
            /// </summary>
            private Deque<TItemType> _deque;

            /// <summary>
            /// Size of the _blocks in the _deque
            /// </summary>
            private readonly int _blockSize;

            /// <summary>
            /// Index of the last block in the _deque
            /// </summary>
            private readonly int _lastBlock;

            /// <summary>
            /// End index of the items in the _deque's last block
            /// </summary>
            private readonly int _lastBlockEndIndex;

            /// <summary>
            /// Index of the block the enumerator currently is in
            /// </summary>
            private int _currentBlockIndex;

            /// <summary>
            /// Reference to the block being enumerated
            /// </summary>
            private TItemType[] _currentBlock;

            /// <summary>
            /// Index in the current block
            /// </summary>
            private int _subIndex;

#if DEBUG
            /// <summary>
            /// Version the _deque is expected to have
            /// </summary>
            private int _expectedVersion;
#endif
        }

        #endregion // local classes Enumerator

        #region local fields

        /// <summary>
        /// Size of a single deque block
        /// </summary>
        private readonly int _blockSize;

        /// <summary>
        /// Memory _blocks being used to store the deque's data
        /// </summary>
        private readonly List<TItemType[]> _blocks;

        /// <summary>
        /// Starting index of data in the first block
        /// </summary>
        private int _firstBlockStartIndex;

        /// <summary>
        /// End index of data in the last block
        /// </summary>
        private int _lastBlockEndIndex;

#if DEBUG
        /// <summary>
        /// Used to detect when enumerators go out of sync
        /// </summary>
        private int _version;
#endif

        #endregion // local fields

        #region properties

        /// <summary>
        /// Number of items contained in the double ended queue
        /// </summary>
        public int Count { get; private set; }

        /// <summary>
        /// Accesses an item by its index
        /// </summary>
        /// <param name="index">Index of the item that will be accessed</param>
        /// <returns>The item at the specified index</returns>
        public TItemType this[int index]
        {
            get
            {
                int blockIndex, subIndex;
                FindIndex(index, out blockIndex, out subIndex);

                return _blocks[blockIndex][subIndex];
            }
            set
            {
                int blockIndex, subIndex;
                FindIndex(index, out blockIndex, out subIndex);

                _blocks[blockIndex][subIndex] = value;
            }
        }

        /// <summary>
        /// The first item in the double-ended queue
        /// </summary>
        public TItemType _First
        {
            get
            {
                if (Count == 0)
                {
                    throw new InvalidOperationException("The deque is empty");
                }
                return _blocks[0][_firstBlockStartIndex];
            }
        }

        /// <summary>
        /// The last item in the double-ended queue
        /// </summary>
        public TItemType _Last
        {
            get
            {
                if (Count == 0)
                {
                    throw new InvalidOperationException("The deque is empty");
                }
                return _blocks[_blocks.Count - 1][_lastBlockEndIndex - 1];
            }
        }

        #endregion // properties

        #region constructors

        /// <summary>
        /// Initializes a new deque
        /// </summary>
        public Deque()
            : this(512)
        {
        }

        /// <summary>
        /// Initializes a new deque using the specified block size
        /// </summary>
        /// <param name="blockSize">Size of the individual memory _blocks used</param>
        public Deque(int blockSize)
        {
            _blockSize = blockSize;

            _blocks = new List<TItemType[]> { new TItemType[_blockSize] };
        }

        #endregion //constructors

        #region local methods

        /// <summary>
        /// Copies the contents of the deque into an array
        /// </summary>
        /// <param name="array">Array the contents of the deque will be copied into</param>
        /// <param name="arrayIndex">Array index the deque contents will begin at</param>
        public void CopyTo(TItemType[] array, int arrayIndex)
        {
            if (Count > (array.Length - arrayIndex))
            {
                throw new ArgumentException(
                    "Array too small to hold the collection items starting at the specified index"
                    );
            }

            if (_blocks.Count == 1)
            {
                // Does only one block exist?

                // Copy the one and only block there is
                Array.Copy(
                    _blocks[0], _firstBlockStartIndex,
                    array, arrayIndex,
                    _lastBlockEndIndex - _firstBlockStartIndex
                    );
            }
            else
            {
                // Multiple _blocks exist

                // Copy the first block which is filled from the start index to its end
                int length = _blockSize - _firstBlockStartIndex;
                Array.Copy(
                    _blocks[0], _firstBlockStartIndex,
                    array, arrayIndex,
                    length
                    );
                arrayIndex += length;

                // Copy all intermediate _blocks (if there are any). These are completely filled
                int lastBlock = _blocks.Count - 1;
                for (int index = 1; index < lastBlock; ++index)
                {
                    Array.Copy(
                        _blocks[index], 0,
                        array, arrayIndex,
                        _blockSize
                        );
                    arrayIndex += _blockSize;
                }

                // Copy the final block which is filled from the beginning to the end index
                Array.Copy(
                    _blocks[lastBlock], 0,
                    array, arrayIndex,
                    _lastBlockEndIndex
                    );
            }
        }

        /// <summary>
        /// Obtains a new enumerator for the contents of the deque
        /// </summary>
        /// <returns>The new enumerator</returns>
        public IEnumerator<TItemType> GetEnumerator()
        {
            return new Enumerator(this);
        }

        /// <summary>
        /// Determines whether the provided object can be placed in the deque
        /// </summary>
        /// <param name="value">Value that will be checked for compatibility</param>
        /// <returns>True if the value can be placed in the deque</returns>
        private static bool IsCompatibleObject(object value)
        {
            return ((value is TItemType)
                    || ((value == null) && !typeof(TItemType).IsValueType));
        }

        /// <summary>
        /// Verifies that the provided object matches the deque's type
        /// </summary>
        /// <param name="value">Value that will be checked for compatibility</param>
        private static void VerifyCompatibleObject(object value)
        {
            if (!IsCompatibleObject(value))
            {
                throw new ArgumentException(
                    "Value does not match the deque's type", "value");
            }
        }

        #region deque item insertion

        /// <summary>
        /// Inserts an item at the beginning of the double-ended queue
        /// </summary>
        /// <param name="item">Item that will be inserted into the queue</param>
        public void AddFirst(TItemType item)
        {
            if (_firstBlockStartIndex > 0)
            {
                --_firstBlockStartIndex;
            }
            else
            {
                // Need to allocate a new block
                _blocks.Insert(0, new TItemType[_blockSize]);
                _firstBlockStartIndex = _blockSize - 1;
            }

            _blocks[0][_firstBlockStartIndex] = item;
            ++Count;

#if DEBUG
            ++_version;
#endif
        }

        /// <summary>
        /// Appends an item to the end of the double-ended queue
        /// </summary>
        /// <param name="item">Item that will be appended to the queue</param>
        public void AddLast(TItemType item)
        {
            if (_lastBlockEndIndex < _blockSize)
            {
                ++_lastBlockEndIndex;
            }
            else
            {
                // Need to allocate a new block
                _blocks.Add(new TItemType[_blockSize]);
                _lastBlockEndIndex = 1;
            }

            _blocks[_blocks.Count - 1][_lastBlockEndIndex - 1] = item;
            ++Count;

#if DEBUG
            ++_version;
#endif
        }

        /// <summary>
        /// Inserts the item at the specified index
        /// </summary>
        /// <param name="index">Index the item will be inserted at</param>
        /// <param name="item">Item that will be inserted</param>
        public void Insert(int index, TItemType item)
        {
            int distanceToRightEnd = Count - index;
            if (index < distanceToRightEnd)
            {
                // Are we closer to the left end?
                ShiftLeftAndInsert(index, item);
            }
            else
            {
                // Nope, we're closer to the right end
                ShiftRightAndInsert(index, item);
            }

#if DEBUG
            ++_version;
#endif
        }

        /// <summary>
        ///   Shifts all items before the insertion point to the left and inserts
        ///   the item at the specified index
        /// </summary>
        /// <param name="index">Index the item will be inserted at</param>
        /// <param name="item">Item that will be inserted</param>
        private void ShiftLeftAndInsert(int index, TItemType item)
        {
            if (index == 0)
            {
                AddFirst(item);
            }
            else
            {
                int blockIndex, subIndex;
                FindIndex(index, out blockIndex, out subIndex);

                int firstBlock = 0;
                int blockStart;

                // If the first block is full, we need to add another block
                if (_firstBlockStartIndex == 0)
                {
                    _blocks.Insert(0, new TItemType[_blockSize]);
                    _blocks[0][_blockSize - 1] = _blocks[1][0];
                    _firstBlockStartIndex = _blockSize - 1;

                    blockStart = 1;
                    --subIndex;
                    if (subIndex < 0)
                    {
                        subIndex = _blockSize - 1;
                    }
                    else
                    {
                        ++blockIndex;
                    }
                    ++firstBlock;
                }
                else
                {
                    blockStart = _firstBlockStartIndex;
                    --_firstBlockStartIndex;

                    --subIndex;
                    if (subIndex < 0)
                    {
                        subIndex = _blockSize - 1;
                        --blockIndex;
                    }
                }

                // If the insertion point is not in the first block
                if (blockIndex != firstBlock)
                {
                    Array.Copy(
                        _blocks[firstBlock], blockStart,
                        _blocks[firstBlock], blockStart - 1,
                        _blockSize - blockStart
                        );
                    _blocks[firstBlock][_blockSize - 1] =
                        _blocks[firstBlock + 1][0];

                    // Move all the _blocks following the insertion point to the right by one item.
                    // If there are no _blocks inbetween, this for loop will not run.
                    for (int tempIndex = firstBlock + 1; tempIndex < blockIndex;
                        ++tempIndex)
                    {
                        Array.Copy(
                            _blocks[tempIndex],
                            1,
                            _blocks[tempIndex],
                            0,
                            _blockSize - 1
                            );
                        _blocks[tempIndex][_blockSize - 1] =
                            _blocks[tempIndex + 1][0];
                    }

                    blockStart = 1;
                }

                // Finally, move the items in the block the insertion takes place in
                Array.Copy(
                    _blocks[blockIndex], blockStart,
                    _blocks[blockIndex], blockStart - 1,
                    subIndex - blockStart + 1
                    );

                _blocks[blockIndex][subIndex] = item;
                ++Count;
            }
        }

        /// <summary>
        ///   Shifts all items after the insertion point to the right and inserts
        ///   the item at the specified index
        /// </summary>
        /// <param name="index">Index the item will be inserted at</param>
        /// <param name="item">Item that will be inserted</param>
        private void ShiftRightAndInsert(int index, TItemType item)
        {
            if (index == Count)
            {
                AddLast(item);
            }
            else
            {
                int blockIndex, subIndex;
                FindIndex(index, out blockIndex, out subIndex);

                int lastBlock = _blocks.Count - 1;
                int blockLength;

                // If the lastmost block is full, we need to add another block
                if (_lastBlockEndIndex == _blockSize)
                {
                    _blocks.Add(new TItemType[_blockSize]);
                    _blocks[lastBlock + 1][0] =
                        _blocks[lastBlock][_blockSize - 1];
                    _lastBlockEndIndex = 1;

                    blockLength = _blockSize - 1;
                }
                else
                {
                    blockLength = _lastBlockEndIndex;
                    ++_lastBlockEndIndex;
                }

                // If the insertion point is not in the lastmost block
                if (blockIndex != lastBlock)
                {
                    Array.Copy(
                        _blocks[lastBlock],
                        0,
                        _blocks[lastBlock],
                        1,
                        blockLength
                        );
                    _blocks[lastBlock][0] =
                        _blocks[lastBlock - 1][_blockSize - 1];

                    // Move all the _blocks following the insertion point to the right by one item.
                    // If there are no _blocks inbetween, this for loop will not run.
                    for (int tempIndex = lastBlock - 1; tempIndex > blockIndex;
                        --tempIndex)
                    {
                        Array.Copy(
                            _blocks[tempIndex],
                            0,
                            _blocks[tempIndex],
                            1,
                            _blockSize - 1
                            );
                        _blocks[tempIndex][0] =
                            _blocks[tempIndex - 1][_blockSize - 1];
                    }

                    blockLength = _blockSize - 1;
                }

                // Finally, move the items in the block the insertion takes place in
                Array.Copy(
                    _blocks[blockIndex], subIndex,
                    _blocks[blockIndex], subIndex + 1,
                    blockLength - subIndex
                    );

                _blocks[blockIndex][subIndex] = item;
                ++Count;
            }
        }

        #endregion //deque item insertion

        #region deque item removal

        /// <summary>
        /// Removes all items from the deque
        /// </summary>
        public void Clear()
        {
            if (_blocks.Count > 1)
            {
                // Are there multiple _blocks?

                // Clear the items in the first block to avoid holding on to references
                // in memory unreachable to the user
                for (int index = _firstBlockStartIndex; index < _blockSize;
                    ++index)
                {
                    _blocks[0][index] = default(TItemType);
                }

                // Remove any other _blocks
                _blocks.RemoveRange(1, _blocks.Count - 1);
            }
            else
            {
                // Nope, only a single block exists

                // Clear the items in the block to release any reference we may be keeping alive
                for (
                    int index = _firstBlockStartIndex;
                    index < _lastBlockEndIndex;
                    ++index
                    )
                {
                    _blocks[0][index] = default(TItemType);
                }
            }

            // Reset the counters to restart the deque from scratch
            _firstBlockStartIndex = 0;
            _lastBlockEndIndex = 0;
            Count = 0;

#if DEBUG
            ++_version;
#endif
        }

        /// <summary>Removes the specified item from the deque</summary>
        /// <param name="item">Item that will be removed from the deque</param>
        /// <returns>True if the item was found and removed</returns>
        public bool Remove(TItemType item)
        {
            int index = IndexOf(item);
            if (index == -1)
            {
                return false;
            }

            RemoveAt(index);

#if DEBUG
            ++_version;
#endif

            return true;
        }

        /// <summary>Removes the first item in the double-ended queue</summary>
        public void RemoveFirst()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException(
                    "Cannot remove items from empty deque");
            }

            // This is necessary to make sure the deque doesn't hold dead objects alive
            // in unreachable spaces of its memory.
            _blocks[0][_firstBlockStartIndex] = default(TItemType);

            // Cut off the item from the first block. If the block became empty and it's
            // not the last remaining block, remove it as well.
            ++_firstBlockStartIndex;
            if (_firstBlockStartIndex >= _blockSize)
            {
                // Block became empty
                if (Count > 1)
                {
                    // Still more _blocks in queue, remove block
                    _blocks.RemoveAt(0);
                    _firstBlockStartIndex = 0;
                }
                else
                {
                    // _Last block - do not remove
                    _firstBlockStartIndex = 0;
                    _lastBlockEndIndex = 0;
                }
            }
            --Count;

#if DEBUG
            ++_version;
#endif
        }

        /// <summary>Removes the last item in the double-ended queue</summary>
        public void RemoveLast()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException(
                    "Cannot remove items from empty deque");
            }

            // This is necessary to make sure the deque doesn't hold dead objects alive
            // in unreachable spaces of its memory.
            int lastBlock = _blocks.Count - 1;
            _blocks[lastBlock][_lastBlockEndIndex - 1] = default(TItemType);

            // Cut off the last item in the last block. If the block became empty and it's
            // not the last remaining block, remove it as well.
            --_lastBlockEndIndex;
            if (_lastBlockEndIndex == 0)
            {
                // Block became empty
                if (Count > 1)
                {
                    _blocks.RemoveAt(lastBlock);
                    _lastBlockEndIndex = _blockSize;
                }
                else
                {
                    // _Last block - do not remove
                    _firstBlockStartIndex = 0;
                    _lastBlockEndIndex = 0;
                }
            }
            --Count;

#if DEBUG
            ++_version;
#endif
        }

        /// <summary>Removes the item at the specified index</summary>
        /// <param name="index">Index of the item that will be removed</param>
        public void RemoveAt(int index)
        {
            int distanceToRightEnd = Count - index;
            if (index < distanceToRightEnd)
            {
                // Are we closer to the left end?
                RemoveFromLeft(index);
            }
            else
            {
                // Nope, we're closer to the right end
                RemoveFromRight(index);
            }

#if DEBUG
            ++_version;
#endif
        }

        /// <summary>
        ///   Removes an item from the left side of the queue by shifting all items that
        ///   come before it to the right by one
        /// </summary>
        /// <param name="index">Index of the item that will be removed</param>
        private void RemoveFromLeft(int index)
        {
            if (index == 0)
            {
                RemoveFirst();
            }
            else
            {
                int blockIndex, subIndex;
                FindIndex(index, out blockIndex, out subIndex);

                const int firstBlock = 0;
                int endIndex;

                if (blockIndex > firstBlock)
                {
                    Array.Copy(
                        _blocks[blockIndex], 0,
                        _blocks[blockIndex], 1,
                        subIndex
                        );
                    _blocks[blockIndex][0] =
                        _blocks[blockIndex - 1][_blockSize - 1];

                    for (int tempIndex = blockIndex - 1; tempIndex > firstBlock;
                        --tempIndex)
                    {
                        Array.Copy(
                            _blocks[tempIndex], 0,
                            _blocks[tempIndex], 1,
                            _blockSize - 1
                            );
                        _blocks[tempIndex][0] =
                            _blocks[tempIndex - 1][_blockSize - 1];
                    }

                    endIndex = _blockSize - 1;
                }
                else
                {
                    endIndex = subIndex;
                }

                Array.Copy(
                    _blocks[firstBlock], _firstBlockStartIndex,
                    _blocks[firstBlock], _firstBlockStartIndex + 1,
                    endIndex - _firstBlockStartIndex
                    );

                if (_firstBlockStartIndex == _blockSize - 1)
                {
                    _blocks.RemoveAt(0);
                    _firstBlockStartIndex = 0;
                }
                else
                {
                    _blocks[0][_firstBlockStartIndex] = default(TItemType);
                    ++_firstBlockStartIndex;
                }

                --Count;
            }
        }

        /// <summary>
        ///   Removes an item from the right side of the queue by shifting all items that
        ///   come after it to the left by one
        /// </summary>
        /// <param name="index">Index of the item that will be removed</param>
        private void RemoveFromRight(int index)
        {
            if (index == Count - 1)
            {
                RemoveLast();
            }
            else
            {
                int blockIndex, subIndex;
                FindIndex(index, out blockIndex, out subIndex);

                int lastBlock = _blocks.Count - 1;
                int startIndex;

                if (blockIndex < lastBlock)
                {
                    Array.Copy(
                        _blocks[blockIndex], subIndex + 1,
                        _blocks[blockIndex], subIndex,
                        _blockSize - subIndex - 1
                        );
                    _blocks[blockIndex][_blockSize - 1] =
                        _blocks[blockIndex + 1][0];

                    for (int tempIndex = blockIndex + 1; tempIndex < lastBlock;
                        ++tempIndex)
                    {
                        Array.Copy(
                            _blocks[tempIndex], 1,
                            _blocks[tempIndex], 0,
                            _blockSize - 1
                            );
                        _blocks[tempIndex][_blockSize - 1] =
                            _blocks[tempIndex + 1][0];
                    }

                    startIndex = 0;
                }
                else
                {
                    startIndex = subIndex;
                }

                Array.Copy(
                    _blocks[lastBlock], startIndex + 1,
                    _blocks[lastBlock], startIndex,
                    _lastBlockEndIndex - startIndex - 1
                    );

                if (_lastBlockEndIndex == 1)
                {
                    _blocks.RemoveAt(lastBlock);
                    _lastBlockEndIndex = _blockSize;
                }
                else
                {
                    _blocks[lastBlock][_lastBlockEndIndex - 1] =
                        default(TItemType);
                    --_lastBlockEndIndex;
                }

                --Count;
            }
        }

        #endregion //deque item removal

        #region deque item search

        /// <summary>
        /// Determines whether the deque contains the specified item
        /// </summary>
        /// <param name="item">Item the deque will be scanned for</param>
        /// <returns>True if the deque contains the item, false otherwise</returns>
        public bool Contains(TItemType item)
        {
            return (IndexOf(item) != -1);
        }

        /// <summary>
        ///   Determines the index of the first occurence of the specified item in the deque
        /// </summary>
        /// <param name="item">Item that will be located in the deque</param>
        /// <returns>The index of the item or -1 if it wasn't found</returns>
        public int IndexOf(TItemType item)
        {
            if (_blocks.Count == 1)
            {
                // Only one block to scan?
                int length = _lastBlockEndIndex - _firstBlockStartIndex;
                int index = Array.IndexOf<TItemType>(
                    _blocks[0],
                    item,
                    _firstBlockStartIndex,
                    length
                    );

                // If we found something, we need to adjust its index so the first item in
                // the deque always appears at index 0 to the user
                if (index != -1)
                {
                    return (index - _firstBlockStartIndex);
                }
                return -1;
            }
            else
            {
                // At least two _blocks exist

                // Scan the first block for the item and if found, return the index
                int length = _blockSize - _firstBlockStartIndex;
                int index = Array.IndexOf(
                    _blocks[0],
                    item,
                    _firstBlockStartIndex,
                    length
                    );

                // If we found something, we need to adjust its index
                if (index != -1)
                {
                    return (index - _firstBlockStartIndex);
                }

                int lastBlock = _blocks.Count - 1;
                for (int tempIndex = 1; tempIndex < lastBlock; ++tempIndex)
                {
                    index = Array.IndexOf(
                        _blocks[tempIndex],
                        item,
                        0,
                        _blockSize
                        );
                    if (index != -1)
                    {
                        return (index - _firstBlockStartIndex
                                + tempIndex * _blockSize);
                    }
                }

                // Nothing found, continue the search in the 
                index = Array.IndexOf<TItemType>(
                    _blocks[lastBlock],
                    item,
                    0,
                    _lastBlockEndIndex
                    );

                if (index == -1)
                {
                    return -1;
                }
                else
                {
                    return (index - _firstBlockStartIndex
                            + lastBlock * _blockSize);
                }
            }
        }

        /// <summary>
        /// Calculates the block index and local sub index of an entry
        /// </summary>
        /// <param name="index">Index of the entry that will be located</param>
        /// <param name="blockIndex">Index of the block the entry is contained in</param>
        /// <param name="subIndex">Local sub index of the entry within the block</param>
        private void FindIndex(int index, out int blockIndex, out int subIndex)
        {
            if ((index < 0) || (index >= Count))
                throw new ArgumentOutOfRangeException(
                    "Index out of range", "index");

            index += _firstBlockStartIndex;

#if XBOX360
                blockIndex = index / this.blockSize;
                subIndex = index % this.blockSize;
#else
            blockIndex = Math.DivRem(index, _blockSize, out subIndex);
#endif
        }

        #endregion //deque item search

        #region deque interfaces

        #region IEnumerable members

        /// <summary>Obtains a new enumerator for the contents of the deque</summary>
        /// <returns>The new enumerator</returns>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        #endregion

        #region IList Members

        /// <summary>Adds an item to the deque</summary>
        /// <param name="value">Item that will be added to the deque</param>
        /// <returns>The index at which the new item was added</returns>
        int IList.Add(object value)
        {
            VerifyCompatibleObject(value);

            AddLast((TItemType)value);
            return Count - 1;
        }

        /// <summary>Checks whether the deque contains the specified item</summary>
        /// <param name="value">Item the deque will be scanned for</param>
        /// <returns>True if the deque contained the specified item</returns>
        bool IList.Contains(object value)
        {
            return IsCompatibleObject(value) && Contains((TItemType)value);
        }

        /// <summary>Determines the index of the item in the deque</summary>
        /// <param name="value">Item whose index will be determined</param>
        /// <returns>The index of the specified item in the deque</returns>
        int IList.IndexOf(object value)
        {
            if (IsCompatibleObject(value))
            {
                return IndexOf((TItemType)value);
            }
            return -1;
        }

        /// <summary>Inserts an item into the deque at the specified location</summary>
        /// <param name="index">Index at which the item will be inserted</param>
        /// <param name="value">Item that will be inserted</param>
        void IList.Insert(int index, object value)
        {
            VerifyCompatibleObject(value);
            Insert(index, (TItemType)value);
        }

        /// <summary>Whether the deque has a fixed size</summary>
        bool IList.IsFixedSize
        {
            get { return false; }
        }

        /// <summary>Whether the deque is read-only</summary>
        bool IList.IsReadOnly
        {
            get { return false; }
        }

        /// <summary>Removes the specified item from the deque</summary>
        /// <param name="value">Item that will be removed from the deque</param>
        void IList.Remove(object value)
        {
            if (IsCompatibleObject(value))
            {
                Remove((TItemType)value);
            }
        }

        /// <summary>Accesses an item in the deque by its index</summary>
        /// <param name="index">Index of the item that will be accessed</param>
        /// <returns>The item at the specified index</returns>
        object IList.this[int index]
        {
            get { return this[index]; }
            set
            {
                VerifyCompatibleObject(value);
                this[index] = (TItemType)value;
            }
        }

        #endregion

        #region ICollection<TItemType> Members

        /// <summary>Adds an item into the deque</summary>
        /// <param name="item">Item that will be added to the deque</param>
        void ICollection<TItemType>.Add(TItemType item)
        {
            AddLast(item);
        }

        /// <summary>Whether the collection is read-only</summary>
        bool ICollection<TItemType>.IsReadOnly
        {
            get { return false; }
        }

        #endregion

        #region ICollection Members

        /// <summary>Copies the contents of the deque into an array</summary>
        /// <param name="array">Array the contents of the deque will be copied into</param>
        /// <param name="index">Index at which writing into the array will begin</param>
        void ICollection.CopyTo(Array array, int index)
        {
            if (!(array is TItemType[]))
            {
                throw new ArgumentException("Incompatible array type", "array");
            }

            CopyTo((TItemType[])array, index);
        }

        /// <summary>Whether the deque is thread-synchronized</summary>
        bool ICollection.IsSynchronized
        {
            get { return false; }
        }

        /// <summary>Synchronization root of the instance</summary>
        object ICollection.SyncRoot
        {
            get { return this; }
        }

        #endregion

        #endregion

        #endregion //local methods
    }
}